//tinh de quy
#include <stdio.h>
#include <conio.h>
//#include <D:\Cac mon hoc\visual\C va C++\CTDl\nganxep.cpp>
//khai bao Stack bang mang
#define MaxLength 100
typedef char ElementType;//typedef float ElementType;
//typedef struct
//{
	//int n;
	//int k;	
//}ElementType;

typedef struct
{
	ElementType Elements[MaxLength];
	int Top_idx;
}Stack;
void MakeNull_Stack(Stack *S)
{
	S->Top_idx = MaxLength;
}
int Empty_Stack(Stack S)
{
	return (S.Top_idx == MaxLength);
}
//kiem tra day
int Full_Stack(Stack S)
{
	return (S.Top_idx == 0);
}
//them phan tu vao ngan xep
void Push(ElementType X, Stack *S)
{
	if(Full_Stack(*S))	printf("\nLoi!Stack khong the them!");
	else
	{
		S->Top_idx = (S->Top_idx - 1);
		S->Elements[S->Top_idx] = X;
	}
}
//xoa phan tu khoi ngan xep
void Pop(Stack *S)
{
	if(Empty_Stack(*S)) printf("\nLoi!Stack rong!");
	else
	{
		S->Top_idx = (S->Top_idx + 1);
	}
}
//lay noi dung phan tu tai dinh ngan xep
ElementType Top(Stack S)
{
	if(!Empty_Stack(S))	return S.Elements[S.Top_idx];
	else
	{
		printf("\nLoi!Stack rong");
		//return NULL;
	}
}
//cac ham de quy
int GiaiThua(int n);
int Fibo(int f);
int ToHop(int k, int n);
//khu de quy
long GiaiThuaKhuDeQuy(int n);
long FibonaciKhuDeQuy(int n);
int ToHopKhuDeQuy(int n, int k);
main()
{
	int chon,n,f,u,v;
	int n1,f1,u1,v1;
	int kq=1,kq2=1,kq3=1;
	printf("\t\t\tHello!Chao ban den voi he thong!");
	do
	{
		printf("\n---Chuong trinh de quy: ");
		printf("\n1. Tinh giai thua");
		printf("\n2. Tim phan tu day Fibonaci");
		printf("\n3. Tinh to hop chap k cua n");
		printf("\n---Chuong trinh dung Stack de khu de quy: ");
		printf("\n4. Tinh giai thua");
		printf("\n5. Tim phan tu day Fibonaci");
		printf("\n6. Tinh to hop chap k cua n");
		printf("\n-------");
		printf("\n7. Thoat");
		printf("\nMoi ban chon: ");
		scanf("%d",&chon);
		switch(chon)
		{
			case 1:
				printf("--Ban chon tinh giai thua dung de quy:\n");
				printf("Moi ban nhap n: ");
				scanf("%d",&n);
				if(n<0)	printf("Khong co giai thua so am!\n");
				else
				{
					kq = GiaiThua(n);
					printf("Giai thua cua %d la: %d",n,kq);
				}
				break;
			case 2:
				//printf("--Ban chon tinh giai thua dung de quy:\n");
				printf("--Tim so phan tu day Fibonaci dung de quy:\n");
				printf("Moi ban nhap so phan tu cua day: ");
				scanf("%d",&f);
				if(f<0)	printf("Ban nhap khong hop le!\n");
				else
				{
					printf("\nSo phan tu day Fibonaci tu 1 --> %d la: ",f);
					for(int i=1;i<=f;i++)
					{
						kq2 = Fibo(i);
						printf("%d  ",kq2);
					}
					
				}
				break;
			case 3:
				//printf("--Ban chon tinh giai thua dung de quy:\n");
				printf("--Tinh to hop chap k cua n dung de quy:\n");
				printf("Nhap k: ");
				scanf("%d",&u);
				printf("Nhap n: ");
				scanf("%d",&v);
				if(u<=0 || v<= 0 || v<=u)	printf("Ban nhap gia tri khong hop le!\n");
				else
				{
					kq3 = ToHop(u,v);
					printf("To hop chap %d cua %d la: %d",u,v,kq3);
				}
				break;
			case 4:
				printf("--Tinh giai thua dung Stack: \n");
				printf("Nhap n: ");
				scanf("%d",&n1);
				if(n1<0)	printf("Khong co giai thua so am!\n");
				else
				{
					printf("Giai thua cua %d la: %ld",n1,GiaiThuaKhuDeQuy(n1));
				}
				break;
			case 5:
				printf("--Tim so phan tu day Fibonaci dung Stack: \n");
				printf("Nhap so phan tu: ");
				scanf("%d",&f1);
				if(f1<0)	printf("Ban nhap khong dung!\n");
				else
					printf("Day so Fibonaci tu 1 --> %d la: ",f1);
					for(int i=1;i<=f1;i++)
						printf("%ld  ",FibonaciKhuDeQuy(i));
				break;
			case 6:
				printf("--Tinh to hop chap k cua n dung Stack: \n");
				printf("Nhap k: ");
				scanf("%d",&u1);
				printf("Nhap n: ");
				scanf("%d",&v1);
				if(u1>v1 || u1<0 || v1<0)	printf("Nhap khong dung!\n");
				else
					printf("To hop chap %d cua %d la: %ld",u1,v1,ToHopKhuDeQuy(v1,u1));
				break;
			case 7:
				printf("Ban da thoat khoi he thong!\nGood bye");
				break;
			default:
				printf("\nBan nhap ngoai pham vi cho phep!\nMoi ban nhap lai");
				break;
		}
	}while(chon != 7);
	getch();
}
int GiaiThua(int n)
{
    if(n<=0) return 1;
    else return n*GiaiThua(n-1);
}
int Fibo(int f)
{
    if(f==0 || f ==1) return 1;
    else return Fibo(f-1) + Fibo(f-2);
}
int ToHop(int k, int n)
{
    if(k==n) return 1;
    else if(k==1) return n;
    else return ToHop(k,n-1) + ToHop(k-1,n-1);
}
//dung Stack de khu de quy
long GiaiThuaKhuDeQuy(int n)
{
     Stack s;
     MakeNull_Stack(&s);
     if(n == 0 || n == 1)
          return 1;
     else
     {
         while(n != 1)
         {
                 Push(n,&s);
                 n--;
         }
         while(!Empty_Stack(s))
         {
                 n = n*Top(s);
                 Pop(&s);              
         }
     }
     return n;
}
long FibonaciKhuDeQuy(int n)
{
     Stack s;
     int s1, s2, s3;
     MakeNull_Stack(&s);
     if(n == 0 || n == 1) return n;
     else
     {
         Push(n,&s);
         while(n != 0)
         {
                 n--;
                 Push(n, &s);
         }
         if(Top(s) != 2)
         {
                   s2 = Top(s);
                   Pop(&s);
                   s3 = Top(s);
                   Pop(&s);
         }
         while(!Empty_Stack(s))
         {
                               s1 = s2+s3;
                               s2 = s3;
                               s3 = s1;
                               Pop(&s);
         }
     }
     return s1;
}

int ToHopKhuDeQuy(int n, int k)
{
    Stack s;
    MakeNull_Stack(&s);
    int s1 = 1,i;
    if(k==n) return 1;
    else if(k==1) return n;
    else
    {
        while(k != 1)
        {
                 Push(k,&s);
                 k--;
                 //Push(n,&s);
        }
        do
        {
        //if(!Empty_Stack(s))
        //{
            	for(i=1;i<=k;i++,n--)
                {
                    s1 = s1*n/i;
                    Pop(&s);   
                }  
		//}      
        }while(!Empty_Stack(s));
    }
    return s1;
}
